1. Field of the Invention
The present invention relates generally to networking environments in which one or more Network Access Devices compete for limited Network Access Channels; more specifically, it relates to allocating and managing bandwidth, for example, for shared Network Access Channels on a local area network (“LAN”).
2. Description of Related Art
Referring now to the drawings, FIG. 1 depicts a simplified networking environment 10 which illustrates in a preferred embodiment of the present invention. More specifically, one or more computers 12, 14, 16, 18, . . . initiate one or more respective network sessions 20, 22, 24, 26, . . . with a communications network such as the Internet 28. Representative network sessions 20, 22, 24, 26, . . . include web browsing sessions, electronic mail (“e-mail”) sessions, file transfer protocol (“FTP”) sessions, and video streaming (“VS”) sessions, among others. Each session involves sending and receiving one or more data packets as part of the network session 20, 22, 24, 26, . . . with one or more other computers (not shown) similarly connected to the networking environment 10.
While the Internet 28 spans the globe, its network of networks connect to one another via electronic pathways that facilitate exchanges of information, files, and other types of data that are transferred through the network sessions 20, 22, 24, 26, . . . . To be “connected” to the Internet 28 means that a computer 12, 14, 16, 18, . . . has access to these electronic pathways. In nearly every networking environment 10, the computers 12, 14, 16, 18, . . . share one or more common Network Access Channels (“NAC”) 30 at a shared Network Access Device (“NAD”) 32 or other network gateway. Known NACs include, for example, a T-1 or digital subscriber line (“DSL”). Known NADs include, for example, cable modes, wireless devices, and other similar devices.
Data packets flow along the electronic pathways according to various well-known protocols, such as the Transmission Control Protocol (“TCP”) and Internet Protocol (“IP”). While the IP functions route the data packets to specified destinations, the TCP functions to break down and reassembles them at respective senders and receivers. Most data transfers over the Internet 28 employ TCP/IP because the Internet 28 is a packet-switched communications network, meaning there are no single, unbroken connections between senders and receivers. Instead, when information is broken down into small data packets for transmission, each individual packet is commonly sent over a different pathway, all at approximately the same time. Because the packets traverse different paths, they commonly arrive out of order. In circuit-switched networks, on the other hand, such as traditional phone lines, a specific part of the network is dedicated in its entirety to a particular sender and receiver as long as a connection therebetween is maintained; in these circuit-switched networks, individual data packets are sent and received sequentially.
A common networking environment 10 can be connected in numerous ways. For example, LANs often join regional networks (e.g., a wide area network (“WAN”)) in order to provide better service and maximize efficiencies. A variety of leased lines commonly connect LANs to WANs and WANs to the World Wide Web (“WWW”). These leased lines may include a single telephone line or a complex fiber-optic cable having microwave linking and satellite transmission capabilities. High-speed “backbones” and other high-capacity lines carry enormous amounts of traffic across the network 10, such as the very high-speed backbone network service (“vBNS”).
When information is broken into data packets according to the TCP for transmission, the packets commonly travel from a LAN through the many levels of the network 10. Various hardware and software components, including hubs, bridges, gateways, repeaters, and routers, process the packets and ensure their delivery at specified destinations. Hereinafter, such components will be referred to as head-end devices (“HED”) 34, although they are not intended to be limited to such. Like NADs 32, HEDs 34 commonly share one or more NACs such as, for example, a DSL Access Multiplexer (DSLAM) or Asynchronous Transfer Mode (“ATM”) Data Switch.
It is often difficult for NADs 32, which allocate and manage upstream traffic, to predict or control the download/arrival rate of data packets from the Internet 28. As a result, the NAD 32 is commonly unable to allocate an efficient amount of bandwidth from the total amount of bandwidth available across its NAC 30. This problem arises because WAN links between NADs 32 and HEDs 34 have limited bandwidth. Thus, for upward traffic sent from a LAN to the Internet 28, congestion traffic traditionally occurs at the NAD 32 whenever the bandwidth required for the data packet's transmission exceeds the available WAN link bandwidth.
Similarly, it is often difficult for HEDs 34, which allocate and manage downstream traffic, to predict or control the upload/serving rate of data packets from a LAN. As a result, the HED 34 is commonly unable to allocate an efficient amount of bandwidth from the total amount of bandwidth available across its NAC 36. This problem arises because WAN links between NADs 32 and HEDs 34 have limited bandwidth. Thus, for downward traffic sent from the Internet 28 to a LAN, congestion traffic traditionally occurs at the HED 34 whenever the bandwidth required for the data packet's transmission exceeds the available WAN link bandwidth.
For example, if a network session 20, 22, 24, 26, . . . requires a certain amount of bandwidth for successful transmission, the traditional NAD 32 has no mechanisms with which to control the HED 34 or monitor congestion at the network 10. As a result, overburdened HEDs 34 commonly drop data packets before transmitting them to NADs 32. More specifically, if a specific NAD 32 is configured for a 512 Kb/sec SV transfer at the same time another user downloads one or more large files in a FTP network session, the HED 34 could be forced to compromise both data transmissions to the NAD 32. Even if the NAD 32 confined the FTP session to ensure sufficient local bandwidth for the SV network session, present-day NADs 32 lack the power to effectively control and monitor traffic congestion at the HED 34.
In addition, most NADs 32 and HEDs 34 regard each data packet as equally important regardless of the host that sent the packet or the network session 20, 22, 24, 26, . . . to which the packet belongs. These devices traditionally have only one input queue and only one output queue for both directions. When a data packet comes in, for example, the NAD 32 appends it at the end of its input queue where it waits to be forwarded with other data packets. While this traditional algorithm sufficed when there were only a few best-effort protocols in use, such as FTP and SMTP, it is less sufficient as increased digital content is shared within the networking environment 10 and delivered via the many different multimedia-streaming protocols that are available today. These multimedia-streaming protocols, such as Video Conferencing and Voice-over-IP applications, commonly require consistent downloading rates, delays, and delay jitters. Furthermore, even for best-effort protocols, more and more business users demand differentiation and prioritization between different types of network traffic. For example, on-line transactions may require preferential treatment over regular web-browsing sessions.
As a result of the problems and shortcoming typified by the foregoing, even small outgoing traffic bursts can abuse bandwidth allocations at the NAD 32 and HED 34. Moreover, most traditional NADs 32 and HEDs 34 employ identical algorithms to predict respective download/arrival rates and upload/serving rates.
While numerous efforts have been aimed at solving these problems and shortcomings, most have focused exclusively on Internet-wide solutions, such as Qualify of Service (“QoS”), Differentiated Service (“DiffServ”), different kinds of feedback mechanisms, Admission Control, Resource Reservation, and other scheduling algorithms. Implementation of an Internet-wide solution, however, would require worldwide adoption of the new algorithm or implementation. Even still, such Internet-wide solutions generally fail to differentiate between network sessions that originate from a common host. While several data flows have been prioritized on selective core routers, these solutions still fail to control and allocate the NAC 30.
What is required, then, is a bandwidth management and allocation mechanism that operates on a NAD 32, independently of a HEDs 34. And since NADs 32 and HEDs 34 are usually controlled by different parities, it is also highly desirable to control both the upstream and downstream data flows at a single device. In this way, the bandwidth management and allocation mechanism can be deployed immediately, and it is easier to maintain and upgrade such a mechanism subsequently. Furthermore, business and other entities can decrease independent serviced providers (“ISP”) service fees and avoid risking disclosing confidential secerets by implementing bandwidth management solely at their own NAD 32. What is needed therefore, is an accurate system and method for predicting download/arrival rates and upload/serving rates so that bandwidth can be allocated efficiently in limited bandwidth networking environments 10. It is also desirable to reduce or eliminate bursty network traffic and provide prioritized traffic routing according to a port or other number, e.g. a TCP port number. It also remains desirable to allocate available bandwidth among network capable devices based on individualized and customized user requirements.
The foregoing and other objects, advantages, and aspects of the present invention will become apparent from the following description. In the description, reference is made to the accompanying drawings which form a part hereof, and in which there is shown, by way of illustration, a preferred embodiment of the present invention. Such embodiment does not represent the full spirit or scope of the invention, however, and reference must also be made to the claims herein for properly interpreting the spirit and scope of this invention.